// @algorithm @lc id=391 lang=cpp 
// @title perfect-rectangle


// #define print(...)
// @test([[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]])=true
// @test([[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]])=false
// @test([[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]])=false
// @test([[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]])=false
using pt = uint64_t;
#define PT(x,y) ( (pt(uint32_t(x))<<32) | uint32_t(y) )
#define PTS(rc) multimap<int,int>({ {rc[0],rc[1]}, {rc[0],rc[3]}, {rc[2],rc[1]}, {rc[2],rc[3]} })
class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        print("\nrects=", rectangles, "\n")
        unordered_map<pt, int> ptn;
        vector<int> out(rectangles[0]);
        int64_t sumArea = 0;
        for(auto & rc : rectangles){
            for(int i=0; i<2; i++) out[i] = min(out[i], rc[i]);
            for(int i=2; i<4; i++) out[i] = max(out[i], rc[i]);
            sumArea += int64_t(rc[2]-rc[0])*(rc[3]-rc[1]);
            for(auto &[x,y] : PTS(rc))
                ptn[ PT(x,y) ]++;
        }
        if(sumArea != int64_t(out[2]-out[0])*(out[3]-out[1]))
            return false;
        for(auto &[x,y] : PTS(out)){
            print("out<", x, ",", y, ">=", ptn[PT(x,y)], "\n")
            if(!ptn.count(PT(x,y))) return false;
        }
        for(auto &[x,y] : PTS(out))
            ptn.erase(PT(x,y));
        for(auto &[p,n] : ptn){
            print("ptn<", p>>32, ",", p&0xFFFF, ">=", n, "\n")
            if(n!=2 && n!=4)
                return false;
        }
        return true;
    }
};